/*
 * @lc app=leetcode.cn id=496 lang=java
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start
class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int[] greater = nextGreaterElement(nums2);
        HashMap<Integer,Integer> greaterMap = new HashMap<>();
        for(int i  = 0;i<nums2.length;i++){
            greaterMap.put(nums2[i],greater[i]);
        }
        int[] res = new int[nums1.length];
        for(int i = 0;i < nums1.length;i++){
            res[i] = greaterMap.get(nums1[i]);
        }
        return res;
    }
    
    private int[] nextGreaterElement(int[] nums){
        int n = nums.length;
        // 存放答案的数组
        int[] res = new int[n];
        Stack<Integer> s = new Stack<>();
        for(int i = n-1;i>=0;i--){
            while(!s.isEmpty() && s.peek() <= nums[i]){
                s.pop();
            }
            res[i] = s.isEmpty() ? -1:s.peek();
            s.push(nums[i]);
        }
        return res;
    }
}
// @lc code=end

